Set Mismatch
Problem Descriptionβ
You have a set of integers s
, which originally contains all the numbers from 1 to n
. Unfortunately, due to some error, one of the numbers in s
got duplicated to another number in the set, which results in repetition of one number and loss of another number.
You are given an integer array nums
representing the data status of this set after the error.
Find the number that occurs twice and the number that is missing and return them in the form of an array.
Examplesβ
Example 1:
Input: nums = [1,2,2,4]
Output: [2,3]
Example 2:
Input: nums = [1,1]
Output: [1,2]
Constraintsβ
2 <= nums.length <= 10^4
1 <= nums[i] <= 10^4
Solution for Find Error Numbers Problemβ
To solve this problem, you need to identify the duplicated number and the missing number in the array.
Approach: Counting Frequencyβ
- Count Frequencies: Use a dictionary or a list to count the frequency of each number in the array.
- Identify Duplicated and Missing Numbers:
- The number with a frequency of 2 is the duplicated number.
- The number with a frequency of 0 (among the numbers from 1 to n) is the missing number.
Brute Force Approachβ
The brute force approach involves iterating over the numbers from 1 to n
and checking their frequency in the given array. This can be achieved by:
- Initializing an array to count the frequency of each number.
- Iterating through the input array to update the frequency count.
- Checking which number has a frequency of 2 (the duplicated number) and which number has a frequency of 0 (the missing number).
Optimized Approachβ
The optimized approach avoids using extra space and iterates through the input array only twice:
- Iterate through the array and mark the corresponding indices as visited by flipping the sign of the elements.
- In the second pass, the index with a positive value indicates the missing number, and the duplicate can be identified by the repeated index encountered in the first pass.
Code in Different Languagesβ
- C++
- Java
- Python
class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
int n = nums.size();
vector<int> freq(n + 1, 0);
vector<int> result(2, 0);
for (int num : nums) {
freq[num]++;
}
for (int i = 1; i <= n; i++) {
if (freq[i] == 2) result[0] = i;
else if (freq[i] == 0) result[1] = i;
}
return result;
}
};
class Solution {
public int[] findErrorNums(int[] nums) {
int[] freq = new int[nums.length + 1];
int[] result = new int[2];
for (int num : nums) {
freq[num]++;
}
for (int i = 1; i < freq.length; i++) {
if (freq[i] == 2) result[0] = i;
else if (freq[i] == 0) result[1] = i;
}
return result;
}
}
class Solution:
def findErrorNums(self, nums: List[int]) -> List[int]:
freq = [0] * (len(nums) + 1)
result = [0, 0]
for num in nums:
freq[num] += 1
for i in range(1, len(freq)):
if freq[i] == 2:
result[0] = i
elif freq[i] == 0:
result[1] = i
return result
Complexity Analysisβ
- Time Complexity: , where
n
is the length of the input array. - Space Complexity: , due to the frequency array used to count occurrences of each number.